#pragma once
#include <vector>
#include<stdlib.h>
#include<iostream>

using namespace std;

template<typename T>
class MergeSort
{
public:
	MergeSort(vector<T> datas)
	{ 
		dataList = datas; 
		mergeSortList();
	}//end constructor

	~MergeSort()
	{
		dataList.clear();
		//delete dataList;
		cout << "Merge sort finishes!" << endl;
	}//end destructor

	vector<T> mergeSortList()
	{
		mergeSort(0, dataList.size() - 1);
		return dataList;
	}//end function

private:
	vector<T> dataList;

	void mergeSort(int lowIndex, int highIndex)
	{
		if (highIndex > lowIndex)
		{
			int middle = (lowIndex + highIndex) / 2; //Calculate middle of vector

			/*Below are codes for displaying middles steps,
			which can be deleted if not wanted: */
			cout << "split:   ";
			displaySubVector(lowIndex, highIndex);
			cout << "         ";
			displaySubVector(lowIndex, middle);
			cout << "         ";
			displaySubVector(middle + 1, highIndex);

			//Back to codes for merge sort:
			mergeSort(lowIndex, middle);
			mergeSort(middle + 1, highIndex);
			merge(lowIndex, middle, highIndex);
		}//end if: Not the recursion base.      
	}//end function

	void merge(int lowIndex, int middle, int highIndex)
	{
		int left = lowIndex; //Index counting left subvector.
		int right = middle + 1; //Index counting right subvector.
		//int combinedIndex = left; //Index of current working vector.
		vector<T> mergeResult;

		/*
			Below are codes displaying merge process, 
			can be deleted if the middle processes are not wanted:
		*/
		cout << "merge:   ";
		displaySubVector(lowIndex, middle);
		cout << "         ";
		displaySubVector(middle + 1, highIndex);

		//Back to codes for merge sort:
		while (left <= middle && right <= highIndex)
		{
			/*Place smaller of the two current elements into result
			and move to next space in vector*/
			if (dataList[left] <= dataList[right])
				mergeResult.push_back(dataList[left++]);
			else
				mergeResult.push_back(dataList[right++]);
		}//end loop: Both left subvector and right subvectors are not scanned up.

		if (left == middle + 1)
		{
			while (right <= highIndex)
				mergeResult.push_back(dataList[right++]);
		}//end if: Left subvector all stored into the merge result, copy the right subvector.
		else
		{
			while (left <= middle)
				mergeResult.push_back(dataList[left++]);
		}//Similar situation

		//Copy values back into original vector:
		for (int index = lowIndex; index <= highIndex; index++)
			dataList[index] = mergeResult[index - lowIndex];

		/*
			Below are codes displaying merge result of subvector,
			can be deleted if the middle processes are not wanted:
		*/
		cout << "         ";
		displaySubVector(lowIndex, highIndex);
		cout << endl;

		mergeResult.clear();
	}//end function

	//Displaying codes, can be deleted if don't want: Display the subvector in a line.
	void displaySubVector(int lowIndex, int highIndex) const{
		for (int i = 0; i < lowIndex; i++)
			cout << "   ";

		for (int i = lowIndex; i <= highIndex; i++)
			cout << " " << dataList[i];

		cout << endl;
	}//end method

};//end class